Markov’s Inq.

P[X≥t]≤E[X]t P[X \geq t] \leq \frac{\mathbb{E}\left[ X\right]}{t}

Proof: E[X]=∑i=1+∞i⋅pX(i)=∑i=1ni⋅pX(i)+∑i=n+∞i⋅pX(i)≥∑i=n+∞i⋅pX(i)≥n∑i=n+∞pX(i)=nP[X≥n] \begin{aligned} \mathbb{E}\left[ X\right] &= \sum_{i=1}^{+\infty} i \cdot p_X(i) = \sum_{i=1}^{n} i \cdot p_X(i) + \sum_{i=n}^{+\infty} i \cdot p_X(i) \geq \sum_{i=n}^{+\infty} i \cdot p_X(i) \geq n \sum_{i=n}^{+\infty} p_X(i) = n P[X \geq n] \end{aligned}

Chebyshev’s Inq.

P[∣X−μ∣≥t]≤σ2t2 P[|X - \mu| \geq t] \leq \frac{\sigma^2}{t^2}

Proof: P[X≥n]≤E[X]nP[X2≥n2]≤E[X2]n2P[(X−μ)2≥n2]=P[∣X−μ∣≥n]≤E[(X−μ)2]n2=σ2n2 \begin{aligned} P[X \geq n] &\leq \frac{\mathbb{E}\left[ X\right]}{n} \\ P[X^2 \geq n^2] &\leq \frac{\mathbb{E}\left[ X^2\right]}{n^2} \\ P[(X - \mu)^2 \geq n^2] = P[|X - \mu| \geq n] &\leq \frac{\mathbb{E}\left[ (X - \mu)^2 \right]}{n^2} = \frac{\sigma^2}{n^2} \\ \end{aligned}

Chernoff’s Inq.

P[X≥t]≤E[eλX]eλt P[X \geq t] \leq \frac{\mathbb{E}\left[ e^{\lambda X} \right]}{e^{\lambda t}}

Proof: P[X≥t]≤E[X]tP[X≥t]=P[λX≥λt]=P[eλX≥eλt]≤E[eλX]eλt \begin{aligned} P[X \geq t] &\leq \frac{\mathbb{E}\left[ X\right]}{t} \\ P[X \geq t] &= P[\lambda X \geq \lambda t] \\ &= P[e^{\lambda X} \geq e^{\lambda t}] \\ &\leq \frac{\mathbb{E}\left[ e^{\lambda X} \right]}{e^{\lambda t}} \\ \end{aligned}

Chernoff’s Inq. for Sums

P[Xn‾≥t]≤(E[eλX1]eλt)n P[\overline{X_n} \geq t] \leq \left( \frac{\mathbb{E}\left[ e^{\lambda X_1} \right]}{e^{\lambda t}} \right)^n

Proof: P[Xn‾≥t]≤E[enλXn‾]enλt≤E[eλ∑i=1nXi]enλt=∏i=1nE[eλXi]enλt=∏i=1nE[eλX1]enλt=(E[eλX1]eλt)n \begin{aligned} P[\overline{X_n} \geq t] &\leq \frac{\mathbb{E}\left[ e^{n\lambda \overline{X_n}}\right]}{e^{n\lambda t}} \\ &\leq \frac{\mathbb{E}\left[ e^{\lambda \sum_{i=1}^{n}X_i}\right]}{e^{n\lambda t}} \\ &= \frac{\prod_{i=1}^{n}\mathbb{E}\left[ e^{\lambda X_i}\right]}{e^{n\lambda t}} \\ &= \frac{\prod_{i=1}^{n}\mathbb{E}\left[ e^{\lambda X_1}\right]}{e^{n\lambda t}} \\ &= \left( \frac{\mathbb{E}\left[ e^{\lambda X_1} \right]}{e^{\lambda t}} \right)^n \end{aligned}

Reference

by Jon